#include <bits/stdc++.h>
using namespace std;

/*
1015. 可被 K 整除的最小整数
已解答
中等
相关标签
premium lock icon
相关企业
提示
给定正整数 k ，你需要找出可以被 k 整除的、仅包含数字 1 的最 小 正整数 n 的长度。

返回 n 的长度。如果不存在这样的 n ，就返回-1。

注意： n 可能不符合 64 位带符号整数。

 

示例 1：

输入：k = 1
输出：1
解释：最小的答案是 n = 1，其长度为 1。
示例 2：

输入：k = 2
输出：-1
解释：不存在可被 2 整除的正整数 n 。
示例 3：

输入：k = 3
输出：3
解释：最小的答案是 n = 111，其长度为 3。
 

提示：

1 <= k <= 105
*/

// 法一
class Solution {
public:
    int smallestRepunitDivByK(int k) {
        // 仅含1 的数 不可能被 2/5 整除
        if (k % 2 == 0 || k % 5 == 0)   return -1;
        int ans = 0, cnt = 0;
        // 循环k次 防止无限循环
        for (int i = 0; i < k; i++) {
            ans = (ans * 10 + 1) % k;   // 构造 取模
            cnt++;
            if (ans == 0) return cnt;   // 找到被k整除 返回长度
        }
        return -1;
    }
};